package algorithms.question.class20;

/**
 * 给定一个字符串str，当然可以生成很多子序列
 * 返回有多少个子序列是回文子序列，空序列不算回文
 * 比如，str = “aba”
 * 回文子序列：{a}、{a}、 {a,a}、 {b}、{a,b,a}
 * 返回5
 *
 * @author guichang
 * @date 2021/8/21
 */

public class Code4_回文子序列 {
    // dp[L][R] str的L~R范围上回文子序列个数
    // 四种情况
    // 选L不选R dp[L][R-1]
    // 不选L选R dp[L+1][R]
    // 不选L不选R dp[L+1][R-1]
    // 选L选R str[L]==str[R]的情况下dp[L+1][R-1]+1，注意中间可为空串
    // 最后四种情况相加就是结果


}